/**
 *    FreeRaven   is an high-power, tiny-footprint, open source  
 *                javascript CSS  selector engine.
 * It supports most CSS3 selectors with more to come. It is realeased
 * under the MIT license and may be used by anyone for opensource or 
 * commercial development.  The only request I have, however, is that
 * when asked, I receive credit for the work done here.  Other than that
 * enjoy! :)
 *
 * @author Rick Allen <stoodder@gmail.com>
 *
 * TODO: 
 * - finish pseudo selectors
 *   - not()
 *   - contains()
 *   - nth-last-child()
 * - allow for * when doing descendants/child sectors (>, +, ~)
 * - Allow for multiple selections, things separated by ,
 * - Use a lookup cache table for element relation between eachother
 */
 (function() 
 {
	//the root element of this select statement
	var root,
	
	//the current partial select based on values found with the 'subcss' string
	select, 
	
	//internal iterator used to push select with new elements
	i, 
	
	//internal iterator used to look at elements returned from offspring or descendant
	//lookups
	j, 
	
	//the state of the selector, used to determine if at a current subcss lookup an element
	//has already been analyzed, necessary for keeping each element in select unique
	state = 0,
	
	//an array containing all strings found in the css string (anything with '' or "" 
	//around it)
	strings, 
	
	//another array like strings that captures all equations (such as 2n or 2n-1) between ( )
	equations,
	
	//the subcss we are currently look at (for now this is a reference to the current 
	//index in parts
	subcss, 
	
	//variable used in selector that represents the tagName to look for (based on what 
	//is in the subcss variable
	tagName, 
	
	//variable used to determine the class name to look for in the current element
	className, 
	
	//variable used to determein and store the id of an element based on the css
	id,
	
	//variable used for storing the name of the attribute to look at in the current element
	attr, 
	
	//varibale used to store the attribute value to look at in the current element
	value, 
	
	//a variable used to store the descendants returned from an element
	descendants, 
	
	//variable used to store the offspring returned from an element
	offspring,
	
	//variable used to hold the current psuedo element
	psuedo,
	
	//variable used to store a parent element
	parent,
	
	//variable used to store the length that a loop
	length,
	
	//internal method used to get an element's next sibling element
	next,
	_next = function(element)
	{
		next = element.nextSibling;
		while( !!next )
		{
			if(next.tagName)
				return next;
			next = next.nextSibling;
		}
		return null;
	},
	
	//internal method used to get an element's previous sibling element
	prev,
	_prev = function(element)
	{
		prev = element.previousSibling;
		while( !!prev )
		{
			if(prev.tagName) return prev;
			prev = prev.previousSibling;
		}
		return null;
	},
	
	//internal method used to get the first child element in the given element
	first,
	_first = function(element)
	{
		first = element.firstChild;
		while( !!first )
		{
			if( first.tagName ) return first;
			first = first.nextSibling;
		}
		return null;
	},
	
	//internal method used to get the first child element in the given element
	last,
	_last = function(element)
	{
		last = element.lastChild;
		while( !!last )
		{
			if( last.tagName ) return last;
			last = last.previousSibling;
		}
		return null;
	},
	
	//method used to get the index of an element within it's parent
	_index = function(element)
	{
		//have we already looked at this element?
		if( element._fr_state == state )
			return element._fr_index; //simply pass back the index
		
		for( var child = _first(element.parentNode), index = 0; child; child = _next(child), ++index )
		{
			child._fr_index = index;
			child._fr_state = state;
		}
		
		return element._fr_index;
	},
	
	//method used to mimic the break; operator
	_break = function() { throw _break; },
	
	// Object used to get a method that will filter and format the current subcss part
	_filter = {
		/*----------------------------------------------------------------*/
		//match all descendant elements
		/*----------------------------------------------------------------*/
		"*" : function() 
		{
			return function(element)
			{
				if( i < 0 )
				{
					select = element.getElementsByTagName("*"),
					i = select.length-1;
					return;
				}
				
				//have we already looked at this element?
				if(element._fr_state == state) return;
				
				//get the necessary decendants
				descendants = element.getElementsByTagName("*"),
				length = descendants.length;
				
				for(j = 0; j < length; ++j)
					( select[++i] = descendants[j] )._fr_state = state;
			}
		},

		/*----------------------------------------------------------------*/
		//match classes
		/*----------------------------------------------------------------*/
		"#" : function()
		{
			//make it into a regular expression to check
			id = subcss.slice(1);
			
			//method used to determine if this element has the requested id
			return function(element)
			{
				if( element.id == id )
					_break( select = [element] );
			};
		},

		/*----------------------------------------------------------------*/
		//match classes
		/*----------------------------------------------------------------*/
		"." : function()
		{	
			//make it into a regular expression to check
			className = " " + subcss.slice(1)+  " ";
			
			return function(element)
			{
				if( (" " + element.className + " ").indexOf(className) > -1 )
					select[++i] = element;
			}
		},

		/*----------------------------------------------------------------*/
		// Math this element and all sub elements, this is used when there
		// is a space between a tag name and a class/id.  since the script
		// divdes the css on the space, we repalce this leading space with
		// an ' character
		/*----------------------------------------------------------------*/
		"'" : function()
		{
			return function(element)
			{
				if( element._fr_state == state) return;
				
				( select[++i] = element )._fr_state = state;
				 
				 descendants = element.getElementsByTagName("*"),
				 length = descendants.length;
				 
				 for( j = 0; j < length; ++j )
					( select[++i] = descendants[j] )._fr_state = state;
			};
			
			/** TODO: This should run faster???? Benchmarks show that it didn't investiagte more for firefox
			id = subcss.slice(2),
			className = " " + id + " ";
			return ({
				"#" : function(element)
				{
					if( element.id == id)
						_break( select = [element] );
					
					if(element.getElementById)
					{
						if( element = element.getElementById(id) )
							_break( select = [element] );
					}
					else
					{
						descendants = element.getElementsByTagName("*"),
						length = descendants.length;
						 
						 for( j = 0; j < length; ++j )
						 {
							element = descendants[j]; 
							if( element._fr_state != state )
							{
								if(element.id == id)
									_break( select = [element] );
								element._fr_state = state;
							}
						}
					}
				},
				"." : function(element)
				{
					if( element._fr_state == state) return;
					
					if( (" " + element.className + " ").indexOf(className) > -1 )
						( select[++i] = element )._fr_state = state;
					
					if( element.getElementsByClassName )
					{
						descendants = element.getElementsByClassName(className),
						length = descendants.length;
						
						for( j = 0; j < length; ++j )
							if( descendants[j]._fr_state != state )
								( select[++i] = descendants[j] )._fr_state = state;
					}
					else
					{
						descendants = element.getElementsByTagName("*"),
						length = descendants.length;
						
						for( j = 0; j < length; ++j )
							if( descendants[j]._fr_state != state && (" " + descendants[j].className + " ").indexOf(className) > -1 )
									( select[++i] = descendants[j] )._fr_state = state;
					
					}
				}
			}[subcss.charAt(1)]);
			/**/
		},

		/*----------------------------------------------------------------*/
		//match children
		/*----------------------------------------------------------------*/
		">" : function(){
			//get the tag name (if there is a >, +, or ~ in front)
			tagName =  subcss.slice(1).toUpperCase();

			return function (element)
			{
				offspring = _first(element);
				while( !!offspring )
				{
					if(offspring.tagName == tagName)
						select[++i] = offspring;
					offspring = _next(offspring);
				}
			};
		},

		/*----------------------------------------------------------------*/
		//match next adjacent element
		/*----------------------------------------------------------------*/
		"+" : function()
		{
			//get the tag name (if there is a >, +, or ~ in front)
			tagName =  subcss.slice(1).toUpperCase();

			return function(element)
			{
				//get the next sibline
				var next = _next(element);

				//if somehting was found and matches the tag, return it
				if ( !!next && next.tagName == tagName)
					select[++i] = next;
			};
		},

		/*----------------------------------------------------------------*/
		//match all next siblings
		/*----------------------------------------------------------------*/
		"~" : function()
		{
			//get the tag name (if there is a >, +, or ~ in front)
			tagName =  subcss.slice(1).toUpperCase();

			return function(element) 
			{
				if(element._fr_state == state)
					return;

				//get the next sibling
				var next = _next(element);

				//look at all next siblings as long as they are valid
				while ( !!next )
				{
					//notify that we've already looked at this element, 
					//and therefor also every element afterwards
					next._fr_state = state;
					
					//does select tag name match the one we're looing for?
					if (next.tagName == tagName)
						select[++i] = next;

					//venture on to the next sibling
					next = _next(next);
				}
			}
		},

		/*----------------------------------------------------------------*/
		//match psuedo selctors
		/*----------------------------------------------------------------*/
		":" : function(){
			psuedo = subcss.toLowerCase();
			
			//return the specified method based on the psuedo selector
			return ({
				//defines the method used to find if select element if the first element of it's parent
				':first-child': function (element) 
				{
					//if there is no more previous elements, select is the first one
					if ( !_prev(element) ) 
						select[++i] = element; //append the matched element
				},
				
				//defined if this element is the last element of it's parent
				':last-child': function (element) 
				{
					//if there is no more elements left, select is the last one
					if ( !_next(element) ) 
						select[++i] = element; //append the matched elemenr
				},
				
				//defines if this element is the only element in its parent
				':only-child': function (element) {
					//if select has no siblings, it is the only child
					if ( !_next(element) && !_prev(element) ) 
						select[++i] = element; //append the matched element
				},
				
				//defines if the given element has no offspring
				':empty' : function(element)
				{
					//this is only empty if no children are found
					if( !_first(element) ) 
						select[++i] = element; //append the matched element
				},
				
				//selects an element if it is an even element of its parent ( 0 indexed )
				':even' : function(element)
				{
					if( _index(element) % 2 == 0 )
						select[++i] = element;
				},
				
				//selects an element if it is an even element of its parent ( 0 indexed )
				':odd' : function(element)
				{
					if( _index(element) % 2 == 1 )
						select[++i] = element;
				},
				//gets all input type elements
				':input' : function(element)
				{
					if( element.tagName.match(/input|textarea|button/i) )
						select[++i] = element;
				},
				//is this element enabled?
				':enabled' : function(element)
				{
					if( element.tagName.match(/input|textarea|button/i) && !element.disabled )
						select[++i] = element;
				},
				//is this element disabled?
				':disabled' : function(element)
				{
					if( element.tagName.match(/input|textarea|button/i) && !!element.disabled ) //Do we really need this regular expression?
						select[++i] = element;				
				},
				//is this element checked?
				':checked' : function(element)
				{
					if( !!element.checked )
						select[++i] = element;
				},
				//is this element not checked?
				':unchecked' : function(element)
				{
					if( ( element.type || "" ).match(/checkbox|radio/i) && !element.checked )
						select[++i] = element;
				},
				':password' : function(element)
				{
					//used to grab all of the password fields
					if( ( element.type || "" ).match(/password/i) )
						select[++i] = element;
				}
				//get the specified method in the hash map, 
			}[psuedo]
			//was this a special selctor such as nth-child()?
			|| (function()
				{
					//get the selctor's equation (might be an equation or simple selector for operations like not and has
					var equation = equations.shift(),
						a = 0,
						b = 0;
					function match_single() { 
						a = parseInt( equation.replace(/ /g, "").match(/\(([0-9]+)\)/)[1] || -1 ); 
					}
					function match_multi() { 
						var matches = equation.replace(/ /g, "").match(/\((([0-9]+)n[+]?)?([0-9]+)?\)/);
						a = parseInt( matches[2] || 0 ); //get a
						b = parseInt( matches[3] || 0 ); 
					}
					return ({
						':nth-child()' : function()
						{
							match_multi();
							var c = a-b; //this is used for the case where we have an+b, it reduces the number of calculations needed
							//return the matching algorithm based on the equation
							return ( a > 0 && b > 0 ?
								//did we match something like #n+# (3n+1)
								function(element) //append the element id it did
								{
									var x = _index(element);
									if( x >= b && ( x + c ) % a < 1 ) select[++i] = element;
								}
							//otherwise did we match something like #n (3n)
							: ( a > 0 ?
								function(element) { if( _index(element) % a == 0 ) select[++i] = element; }
							//lastly just get by index # (3)
							: 	function(element) { if( _index(element) == b ) select[++i] = element; }
							));
						},
						//TODO: This
						':nth-last-child()' : function()
						{
							match_multi();
						},
						//gets all elements who's index is greater then the given index
						':gt()': function()
						{
							match_single();
							return function(element) { if( _index(element) > a ) select[++i] = element; }
						},
						//gets all elements who's index is less than this index
						':lt()': function()
						{
							match_single();
							return function(element) { if( _index(element) < a ) select[++i] = element; }
						},
						//TODO: consider getting rid of these, the same effect can come with a :gt():lt() combo move
						//Gets all elements who's ID is equal to the one given
						':eq()': function()
						{
							match_single();
							return function(element) { if( _index(element) == a ) select[++i] = element;}
						},
						//Gets all elements who's ID is not equal to the one given
						':neq()': function()
						{
							match_single();
							return function(element) { if( _index(element) != a ) select[++i] = element; }
						}
						/**
						* TODO:
						* not
						* has
						* nth-last-child
						*/
					}[psuedo]
						|| function() { select = []; _break() }
					)()
				})()
			)
		},

		/*----------------------------------------------------------------*/
		//match attribute selctor
		/*----------------------------------------------------------------*/
		"[" : function()
		{
			//get the index in the subcss of the '=' (if one exists)
			var index = subcss.indexOf("=");
			
			//if we didn't find one, simply look to see if we have the attrbute
			if(index == -1) 
			{
				//remove the [ and ] on either side of the subcss
				attr = subcss.slice(1,-1).toLowerCase();
				
				//pass back the iteration method to use
				return function (element) 
				{
					//does select attribute exist?
					if ( ( attr == 'class' ? element.className.length > 0  : !!element.getAttribute(attr) ) )
						select[++i] = element; //append the matched element
				};
			}

			var value = strings.shift(); //get the next string off the strings list
			value = value.slice(1,-1);
			
			var func = {
				//return method, does the attribute start with the given cach value?
				"^": function (check) 
				{ 
					return ( check.slice(0, value.length) == value ); 
				},
				//return method, is the value found in a space separated list?
				"~": function (check) 
				{ 
					return ( (" " + check + " ").indexOf(" " + value + " ") > -1 ); 
				},
				//return method, is the check value found at the end of the attribute
				"$": function (check) 
				{ 
					return ( check.slice(-value.length) == value ); 
				},
				//return method, is the check vaule found anywhere in the attribute?
				"*": function (check) 
				{ 
					return ( check.indexOf(value) > -1 ); 
				},
				//return method, is the check value found anywhere in he dash separated attribute
				"|": function (check) 
				{ 
					return ( ("-" + check + "-").indexOf("-" + value + "-") > -1 ); 
				},
				//return method, does the check value NOT exist in the aattribute
				"!": function (check) 
				{ 
					return ( (check).indexOf(value) == -1 ); 
				}
			}[subcss.charAt(index-1)]; //try to get the correct method
			
			//if no method found, resort to the default method and get the correct attribute string
			if( !func )
			{
				//set the checking function to default which is to simply compare the element's attribute 
				//against the requested value
				func = function(check) { return (value == check) };
				attr = subcss.slice(1,-2);
			}
			//otherwise get the attribute and string off the special selector character
			else
			{
				attr = subcss.slice(1,-3);
			}
			
			//pass back he method to match the attribute based on the given selector
			return function (element) 
			{
				//get the attribute of the element
				if ( func( attr == 'class' ? element.className : element.getAttribute(attr) || "" ) )
					select[++i] = element; //append the matched element
			};
		}
	};

	/*----------------------------------------------------------------*/
	// Default filtering method to use, the subcss, if valid, will match a tag name
	/*----------------------------------------------------------------*/
	_defaultFilter = function()
	{
		//get and format the tag name
		tagName = subcss.toUpperCase();
		
		//return the selector method
		return function(element) 
		{	
			if( element == root )
				_break( select = element.getElementsByTagName(tagName) );	
				
			//have we already looked at this element?
			if(element._fr_state == state) return;
			
			descendants = element.getElementsByTagName(tagName),
			length = descendants.length;
			
			//look over the results and only add those who haven't already been added
			for(j = 0; j < length; ++j)
				if( descendants[j]._fr_state != state ) //should be able to get rid of this?
					( select[++i] = descendants[j] )._fr_state = state;
		};
	};
	
	//define the default selector methodology
	function FreeRaven(css, element) 
	{
		//make sure the css is a string
		if (typeof css != 'string') return [];

		//get the root 'context' element
		root = ( !element ? document : ( typeof element == 'object' ? element : document.getElementById(element) ) );
		
		//if the element was invalid, pass back a blank array
		if( !root ) return [];
		
		//do we have access to faster internal methods?
		if( root.querySelectorAll )
			try { return root.querySelectorAll(css) } catch(e) {}
		
		//get all of the strings within the css
		strings = css.match(/("[^"]*")|('[^']*')/g); // get all strings in the css
		css = css.replace(/("[^"]*")|('[^']*')/g, "") //now remove all strings
		equations = css.match(/\([^)]+\)/g); // get all equations ( anything between ( and )
		css = css.replace(/\([^)]+\)/g, "()"); // now remove all of these equations
		
		//start "normalizing" the css string
		css = css	.replace(/\s+(\.|#)/g, "'$1")
					.replace(/([:#.+>[~'])\s*/g, " $1") //put spaces between the necessary characters
					.replace(/\s+/g, " ") //remove all multiple white space
					//.replace(/'\s+(\.|#)/g, "'$1")//NEW
					.replace(/ ?([|^~$*]?=) ?/g, "$1") //if this is an attribtue selector, remove any white space between it.
					.replace(/\[ /, "[") //remove white space between []
					.replace(/ ?(.+) ?/, "$1"); //trim out any leading or trailing space
		
		//if the css is empty, return nothing
		if( css.length == 0 ) return [];
		
		//get each of the parts
		var parts = css.split(" "),
		//reset the subcss parts select iterator
			k = -1;
		
		//TODO: consider caching this result
		//if we're starting with a class or ID just get the descendants, otherwise we must start with the root element
		var _select = 
		({
			"." : function()
			{
				return ( root.getElementsByClassName ?
					root.getElementsByClassName( parts[0].slice(++k+1) )
					//otherwise get everything
					: root.getElementsByTagName("*")
				)
			},
			//if we're starting by looknig for an ID see if there are any browser specific methods to get an element by id
			"#" : function()
			{
				return ( root.getElementById ?
					//can the root grab by id? if so do it!
					[ root.getElementById( parts[0].slice(++k+1)) ]
					//otherwise grab everything
					: root.getElementsByTagName("*")
				)
			}
		}[ css.charAt(0) ]
			//otherwise just pass back the root element, no intial selections are needed
			|| function()
			{
				return [root];
			}
		)();
		/**/
		
		//incremenet through the parts and set the subcss while we can
		while( subcss = parts[++k] )
		{	
			select = [], //reset the subselect
			i = -1; //reset the sub select iterator
			
			try {
				var filter = ( _filter[ subcss.charAt(0) ] || _defaultFilter )(), //execute operations on the current subcss part and return the filter method
					size = _select.length; //store the length of the currently selected elements for faster loops
				
				//iterate through each selected element and apply the current subcss part
				for( var l = 0; l < size; ++l) filter( _select[l] ); //apply the filtering
			//were we intentionally trying to break out? if not propogate the error
			} catch (e) { if( e != _break ) throw e; }
			
			//store the newly selected nodes as the current selected value
			_select = select;
			
			//increment the state (needed for uniqueness of results)
			++state;
			
			//if nothing is left in the selcect then there is no use in contirnuing
			if (_select.length == 0) break;
		}
		
		//return our results
		return _select;
	}
	
	/**
	* Simple method to always get an array back from a FreeRaven execution.
	*
	* @param {String} css A String css selctor
	* @param {String} root The id of the element to be considered the root elemenet
	* 
	* @return {Array} An array version of the results
	*/
	FreeRaven.array = function( css, root )
	{
		var array = [], //the array we will be pasing back
			raven = FreeRaven(css, root), //find the results
			length = raven.length; //store the length for quicker loops
		
		//if this is already an array don't even bother generating one
		if( Object.prototype.toString.call(raven) == '[object Array]' )
			return raven;
		
		//generate the array
		for( var i = 0; i < length; ++i )
			array[i] = raven[i];
		
		//return the result
		return array;
	};
	
	/**
	* Method used to remove the cache within FreeRaven, blank for the non-caching version
	*/
	FreeRaven.clearCache = function() {};
	
	//show the rest of the internets
	window.FreeRaven = FreeRaven;
 })();